package com.zjj.learn.algorithmPlus.segment1.stack;

import java.util.Arrays;
import java.util.Iterator;

/**
 * 基于带哨兵的单向链表实现栈
 * 单向链表头结点 head是哨兵节点，只做标识，不存储真实数据
 *
 * @author zjj_admin
 */
public class LinkedListStack<E> implements Stack<E>, Iterable<E> {


    /**
     * 队列中链表的数据结构
     *
     * @param <E>
     */
    private static class Node<E> {
        /**
         * 当前节点数据
         */
        E value;
        /**
         * 下一个节点
         */
        Node<E> next;

        public Node(E value, Node<E> next) {
            this.value = value;
            this.next = next;
        }
    }

    /**
     * 哨兵节点，思考为什么队列还要定义一个尾节点
     */
    private final Node<E> head;

    /**
     * 栈中的数据个数
     */
    private int size;

    /**
     * 栈的最大容量
     */
    private final int capacity;

    /**
     * 只提供有参构造
     *
     * @param capacity
     */
    public LinkedListStack(int capacity) {
        if (capacity < 0) {
            throw new IndexOutOfBoundsException("capacity 必须大于 0......");
        }
        size = 0;
        this.capacity = capacity;
        head = new Node(null, null);
    }

    /**
     * 压栈：将新添加的数据添加在头结点后面
     *
     * @param value 添加数据
     * @return
     */
    @Override
    public boolean push(E value) {
        if (isFull()) {
            return false;
        }
        Node<E> added = new Node<E>(value, head.next);
        head.next = added;
        //上面两行代码可以简化成一行，head.next = new Node<>(value, head.next);
        size++;
        return true;
    }

    /**
     * 出栈：返回并删除第一个节点数据
     *
     * @return
     */
    @Override
    public E pop() {
        if (isEmpty()) {
            return null;
        }
        Node<E> first = head.next;
        head.next = head.next.next;
        size--;
        return first.value;
    }

    /**
     * 返回第一个元素
     *
     * @return
     */
    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        return head.next.value;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean isFull() {
        return size == capacity;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            Node<E> p = head.next;

            @Override
            public boolean hasNext() {
                return p != null;
            }

            @Override
            public E next() {
                E value = p.value;
                p = p.next;
                return value;
            }
        };
    }

    /**
     * 重写 toString 方法
     *
     * @return
     */
    @SuppressWarnings("all")
    @Override
    public String toString() {
        Node<E> p = head.next;
        E[] a = (E[]) new Object[size];
        int i = 0;
        while (p != null) {
            a[i] = p.value;
            p = p.next;
            i++;
        }
        return Arrays.toString(a);
    }
}
